// 基本思想：经典的分治策略，递归地将当前序列平均分成两半，然后将有序序列两两合并，最终合并成一个有序序列

// 步骤：1. 分割过程：递归地将当前序列平均分成两半，直到子序列长度为1
// 2. 归并过程：从长度为1的有序子序列开始，依次进行两两归并，直到合并成一个长度为n的有序序列


// 时间复杂度：O(nlogn)
// 空间复杂度：O(n)
// 排序稳定性：稳定
function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr
    }
    let mid = Math.floor(arr.length / 2)
    let leftArr = mergeSort(arr.slice(0, mid))
    let rightArr = mergeSort(arr.slice(mid)) 
    return merge(leftArr, rightArr)
}

function merge(leftArr, rightArr) {
    let arr = []
    let leftIndex = 0
    let rightIndex = 0
    while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
        // 将两个有序子序列中较小元素依次插入到结果数组中
        if (leftArr[leftIndex] < rightArr[rightIndex]) {
            arr.push(leftArr[leftIndex])
            leftIndex++
        } else {
            arr.push(rightArr[rightIndex])
            rightIndex++
        }
    }
    if (leftIndex < leftArr.length) {
        arr = [...arr, ...leftArr.slice(leftIndex)]
    }
    if (rightIndex < rightArr.length) {
        // arr.concat(rightArr.slice(rightIndex))
        arr = [...arr, ...rightArr.slice(rightIndex)]
    }
    return arr
}

let arr = [6, 2, 1, 3, 7, 5, 4, 8]
console.log(mergeSort(arr))